// 相比于上两题，最多可以买卖两次，可能性为，买卖0次，1次，2次
// 1. dp数组的下标以及含义，
//     1. 一共有5种状态， 不一定非得第i天买入，而是持有状态， 不一定非得第i天卖出，而是不持有状态
//         0. 没有操作
//         1. 第一次持有股票，
//         2. 第一次不持有股票
//         3. 第二次持有股票
//         4. 第二次不持有股票
//     2. `dp[i][j]`, 表示第i天状态j所剩下的最大现金
// 2. 确定递推公式，
//     1. 确定`dp[i][1]`，第i天，第一次持有股票
//         1. 第i天第一次买入， `dp[i][1] = dp[i-1][0] - price[i]`
//         2. 第i天没有操作，`dp[i][1] = dp[i-1][1]`
//         3. `dp[i][1] = Math.max(dp[i-1][0] - price[i], dp[i-1][1])`
//     2. 确定`dp[i][2]`, 第i天，第一次不持有股票
//         1. 第i天第一次卖出，`dp[i][2] = dp[i-1][1] + price[i]`
//         2. 第i天没有操作, `dp[i][2] = dp[i-1][2]`
//         3. `dp[i][2] = Math.max(dp[i-1][1] + price[i], dp[i-1][2])`
//     3. 确定`dp[i][3]`，第i天，第二次持有股票
//         1. 第i天第二次买入， `dp[i][3] = dp[i-1][2] - price[i]`
//         2. 第i天没有操作，`dp[i][3] = dp[i-1][3]`
//         3. `dp[i][3] = Math.max(dp[i-1][2] - price[i], dp[i-1][3])`
//     4. 确定`dp[i][4]`, 第i天，第二次不持有股票
//         1. 第i天第二次卖出，`dp[i][4] = dp[i-1][3] + price[i]`
//         2. 第i天没有操作, `dp[i][4] = dp[i-1][4]`
//         3. `dp[i][4] = Math.max(dp[i-1][3] + price[i], dp[i-1][4])`
// 3. dp数组初始化
//     1. `dp[0][0] = 0`
//     2. `dp[0][1]` = -prices[0]，第一次买入
//     3. `dp[0][2]` = 0
//     4. `dp[0][3]` =  -prices[0]
//     5. `dp[0][4]` =  0
// 4. 确定遍历顺序，从前到后
// 5. 举例推导
// 最大的情况一定是卖出的状态，两次卖出一定是最后一次卖出最大，因为最后一次卖出包含了第一次卖出，当天买，当天卖
// 时间复杂度：O(n)
// 空间复杂度：O(n × 5)

function maxProfit(prices) {
    let dp = new Array(prices.length).fill(0).map(_ => new Array(5).fill(0))
    dp[0][1] = -prices[0]
    dp[0][3] = -prices[0]
    for (let i = 1; i < prices.length; i++) {
        dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i])        
        dp[i][2] = Math.max(dp[i-1][2], dp[i-1][1] + prices[i])        
        dp[i][3] = Math.max(dp[i-1][3], dp[i-1][2] - prices[i])        
        dp[i][4] = Math.max(dp[i-1][4], dp[i-1][3] + prices[i])        
    }
    return dp[prices.length - 1][4]
}

let prices = [3,3,5,0,0,3,1,4]
console.log(maxProfit(prices))